# include "geometry2d.hpp"

# include <cmath>
# include <list>

# include "slice.hpp"

# include <iostream>

namespace g2 = geometry::d2;

namespace {

  typedef utils::range range;

  std::list<size_t> simplifyCurveImpl(range const range, std::vector<g2::Point> const& v, double const eps) {

    if (range.size() == 2) {
      std::list<size_t> r;
      r.push_back(range[0]);
      r.push_back(range[1]);
      return r;

    } else {
      g2::Line L = g2::Line(v[range[0]], v[range[-1]]);

      size_t mindex = 0;
      double mdist = g2::dist(L, v[range[1]]);
      for (size_t i : range(2, -1)) {
        double const dist = g2::dist(L, v[range[i]]);
        if (dist > mdist) {
          mdist = dist;
          mindex = i;
        }
      }

      if (mdist > eps) {
        std::list<size_t> head = simplifyCurveImpl(range(0, mindex + 1), v, eps);
        std::list<size_t> tail = simplifyCurveImpl(range(mindex), v, eps);
        
        std::copy(++begin(tail), end(tail), std::back_inserter(head));
        return head;

      } else {
        std::list<size_t> r;
        r.push_back(range[0]);
        r.push_back(range[-1]);

        return r;
      }
    }
  }

}


/*! @brief Computes distance between line and points
 */
double g2::dist(g2::Line const& L, g2::Point const& p) {
  double const denom = sqrt(L.cx_ * L.cx_ + L.cy_ * L.cy_);
  return fabs(L(p))/denom;
}



/*! @brief Simplify the curve
 */
std::vector<g2::Point> g2::simplifyCurve(std::vector<Point> const& curve, double const eps) {
  std::vector<Point> simplified;

  if (curve.size() == 2) {
    simplified = curve;
  } else {
    utils::range r = utils::range(0, curve.size());
    std::list<size_t> indexes = simplifyCurveImpl(r, curve, eps);
    for (size_t index : indexes)
      simplified.push_back(curve[index]);
  }

  return std::move(simplified);
}

